#include <vector>
#include <string>
#include <list>

using namespace std;


/**
 * Definition for a binary tree node.
 */
struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode() : val(0), left(nullptr), right(nullptr) {}
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
    TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};


class Codec {  // 采用 DFS 方法
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        string res;
        serializeHelper(root, res);  // use preorder traversal
        return res;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        list<string> data_arr;
        string str;
        for (auto& c : data) {
            if (c == ',') {
                data_arr.push_back(str);
                str.clear();
            } else {
                str.push_back(c);
            }
        }
        if (!str.empty()) {
            data_arr.push_back(str);
            str.clear();
        }
        return deserializeHelper(data_arr);
    }

private:
    void serializeHelper(TreeNode* root, string& str) {
        if (!root) {
            str += "None,";
        } else {
            str += to_string(root->val) + ",";
            serializeHelper(root->left, str);
            serializeHelper(root->right, str);
        }
    }

    TreeNode* deserializeHelper(list<string>& data_arr) {
        if (data_arr.front() == "None") {
            data_arr.erase(data_arr.begin());
            return nullptr;
        }

        TreeNode* root = new TreeNode(stoi(data_arr.front()));
        data_arr.erase(data_arr.begin());
        root->left = deserializeHelper(data_arr);
        root->right = deserializeHelper(data_arr);
        return root;
    }
};
